#!/usr/bin/env python

import random
import sys
from pgap.Chromosone import Chromosone
from pgap.impl.IntegerGene import IntegerGene

"""
	This gene basically represents the order in which the city is visited, i.e.
	cities which order 'a' will be visited before city with order 'b' if 'a'<'b'
"""
class TSPGene(IntegerGene):
	allele = 0 

	def __init__(self):
		self.allele = 0	
	
	def setRandomValue(self):
		index = random.random()*self.upperBound	
		self.allele = index

	def setUpperBound(self,upperBound):
		self.upperBound = upperBound


class TSPCityOrder:

	def __init__(self,order,city):
		self.order = order
		self.city  = city

	def __cmp__(self,other):
		ret = 0

		if self.order.getValue() > other.order.getValue():
			ret = 1
		elif self.order.getValue() < other.order.getValue():
			ret = -1
		
		return ret

	def __str__(self):
		str = "<%d,%s>"	% (self.order.getValue(),self.city)
		return str

	def __repr__(self):
		str = "<%d,%s>"	% (self.order.getValue(),self.city)
		return str


class TSPChromosone(Chromosone):

	def __init__(self,distanceMap):
		self.path	= []	
		self.cityList   = distanceMap.keys()
		cityCount	= len(self.cityList)
		self.distanceMap = distanceMap
		self.genes	 = list()
		for city in distanceMap.keys():
			gene = TSPGene()
			gene.setUpperBound(cityCount - 1)
			self.genes.append(gene)

				
	def clone(self):
		cloneChromo = TSPChromosone(self.distanceMap)

		for gene in self.genes:
			cloneGene = gene.clone()
			cloneChromo.addGene(cloneGene)

		return cloneChromo
	
	def generatePath(self):
		self.path = list()
		index = 0
		for city in self.cityList:
			order = self.genes[index]				
			cityOrder = TSPCityOrder(order,city)
			self.path.append(cityOrder)
			index = index + 1		
		self.path.sort()		

	
	def fitness(self):
		self.generatePath()
		index = 0
		distance = 0
		cityCount = len(self.cityList)		
	
		for pair in self.path:
			if (index == cityCount - 1):
				break	

			cityOrder1 = self.path[index]
			city1	   = cityOrder1.city
			cityOrder2 = self.path[index + 1]
			city2	   = cityOrder2.city
			
			if (cmp(city1,city2) != 0):
				if (self.distanceMap[city1].has_key(city2)):
					d    = self.distanceMap[city1][city2]
				else:
					d    = sys.maxint
			else:
				d = 0

			if (d == sys.maxint):
				distance = sys.maxint
				break
			distance   = distance + d	
			index = index + 1
			
		return distance


	def __str__(self):
		sstr = "<%d,%s>" % (self.fitness(),str(self.path))
		return sstr

	def __repr__(self):
		rep = "<%d,%s>" % (self.fitness(),str(self.path))
		return rep
	
	
		

				
